home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / THINKC / 4_0 / VIVIDUS / QD3D.SIT / qd3d / gouraud.c < prev    next >
C/C++ Source or Header  |  1991-08-17  |  13KB  |  497 lines
  1. #include    <math.h>
  2. #include    "gouraud.h"
  3. #include    <Cqd3dPort.h>
  4.  
  5. int    next (int n, FixedVector v[], int s);
  6. int    prev (int n, FixedVector v[], int s);
  7.  
  8. /*    ======================================================================
  9.  
  10.     Gouraud and line color blending primitives.
  11.     
  12.     This is part of the qd3d Vividus Source Code Library.  See the
  13.     extern qd3d.doc documentation file for usage.  See individual
  14.     routines for routine documentation.
  15.     
  16.     Copyright 1991 by Vividus Consulting.
  17.     
  18.     This is not public domain source code.  You may not copy and
  19.     paste from this source code.  Read your Vividus Licensing
  20.     agreement for details and other restrictions.
  21.  
  22.     ======================================================================    */
  23.     
  24. /*    ======================================================================
  25.  
  26.     WARNING to qd3d users:
  27.     
  28.     Everything in this file is private to the qd3d library and highly
  29.     subject to change.
  30.  
  31.     ======================================================================    */
  32.  
  33. /*    ======================================================================
  34.  
  35.     Explanatory notes:
  36.     
  37.     The qd3d routines in this "gouraud.c" source file discretize
  38.     the "vector" points specified by the external client routines
  39.     to FixedVector points before screen discretization to "int's."
  40.     Internal calculations are calculated using the FixedVector
  41.     representation.  The FixedVector representation is used to:
  42.     ensure no gaps or overlaps between adjacent polygons whose edges
  43.     possess identical endpoints; aid in prevention of gaps and overlaps
  44.     between adjacent polygons whose edges don't possess identical
  45.     endpoints -- this has not fully been evaluated yet; and ensure
  46.     that the last location specified by a dda ends up at the correct
  47.     location -- it increases the accuracy of the dda.  Since
  48.     MC68K processors are internally 32 bits, this doesn't
  49.     drastically decrease performance.  Details of the application
  50.     of this concept are considered proprietary and will not be
  51.     discussed further.
  52.     
  53.     The qd3d routines in this "gouraud.c" source file also use a
  54.     FixedVector discretization of the client indicated color vector.
  55.     This FixedVector representation is the "vector" times 2^15.
  56.     Two^15 is used instead of 2^16 to avoid sign problems.
  57.  
  58.     ======================================================================    */
  59.  
  60. extern unsigned int        *theZBuff;
  61. extern unsigned int        *theZBuffLast;
  62. extern unsigned int        theZBuffWidth;
  63.  
  64. #define    abs(a)    ((a) > 0 ? (a) : -(a))
  65.  
  66. /*
  67.     Some optimization timings:
  68.         Note:  As presently implemented (<910618), the bottleneck for the Gouraud shader
  69.                 is SetCPixel.  Some timings:
  70.         25.67 sec.    When used with SetCPixel.
  71.         9.0x sec.    Doing everything except calling SetCPixel.
  72.         4.5 sec.    Poly's drawn with the xdraw debug code.
  73.         <2 sec.        Poly's drawn with "PaintPoly."
  74.     
  75.         Plot3dPoint is an ideal change point.C
  76. */
  77. /*    ------------------------------------------------------------    */
  78. /*    Routines:                                                        */
  79.  
  80. void
  81. PlotC3dPoint(FixedVector *x, FixedVector *c)
  82. /*
  83.     Plot the 3d point at x with the color identified by c.
  84.     
  85.     Warning:    This is a private function to the qd3d library and is
  86.                 highly subject to change or removal.
  87. */
  88. {
  89.     register unsigned int    *q;
  90.     RGBColor                rgb;
  91.     IntVector                pp;
  92.  
  93.     fv2iv(x, &pp);
  94.     cv2rgb(c, &rgb);
  95.         
  96.     /*    plot 3d point    */
  97.     if (theZBuff) {
  98.         q = theZBuff;
  99.         q += (unsigned long)pp.y * theZBuffWidth;
  100.         q += (unsigned long)pp.x;
  101.         if ( (q < theZBuffLast) && (q >= theZBuff) ) {
  102.             if (pp.z <= *q) {
  103.                 *q = pp.z;
  104.                 SetCPixel(pp.x, pp.y, &rgb);
  105.             }
  106.         }
  107.     } else {
  108.         SetCPixel(pp.x, pp.y, &rgb);
  109.     }
  110. }
  111.  
  112. void
  113. C3dLine(FixedVector *p1, FixedVector *p2, FixedVector *c1, FixedVector *c2)
  114. /*
  115.     This routine draws a color blended line segment from p1 to p2 where
  116.     p1 has color c1 and c2 has color c2.
  117.  
  118.     Warning:    This is a private function to the qd3d library and is
  119.                 highly subject to change or removal.
  120. */
  121. {
  122.     FixedVector    c, dc;
  123.     FixedVector    x, dx;
  124.     
  125.     Boolean        xmajor;    /*    xmajor indicates the slope of the line is < 1.    */
  126.                         /*    this indicate the line is "xmajor."  Otherwise,    */
  127.                         /*    it is "ymajor."                                    */
  128.     int            n;
  129.     Fixed        rw;
  130.     int            i;
  131.  
  132.     FixedVector    fv;
  133.     Fixed        alpha;
  134.     Boolean        agt0;
  135.     
  136.     static Boolean        Debug = false;
  137.         
  138.     if (Debug) {    /*    Speeds up overlap debugging    */
  139.         ForeColor(blackColor);
  140.         PenMode(patXor);
  141.         MoveTo(HiWord(p1->x), HiWord(p1->y));
  142.         LineTo(HiWord(p2->x), HiWord(p2->y));
  143.         return;
  144.     }
  145.  
  146.     fvsub(p2, p1, &dx);
  147.     fvsub(c2, c1, &dc);
  148.     
  149.     xmajor = abs(dx.x) >= abs(dx.y);
  150.     if (xmajor) {
  151.         rw = FixDiv(0x10000L, abs(dx.x));
  152.         n = abs(HiWord(p2->x) - HiWord(p1->x));
  153.     } else {
  154.         rw = FixDiv(0x10000L, abs(dx.y));
  155.         n = abs(HiWord(p2->y) - HiWord(p1->y));
  156.     }
  157.     fvscale(rw, &dx, &dx);    
  158.     fvscale(rw, &dc, &dc);
  159.                             /*    dx.y or dx.x should == 1 or there will be
  160.                                 cumulative roundoff errors.
  161.                             */
  162.  
  163.     /*    Adjust so that increments will hit on xmajor half pixels.            */
  164.     /*        This is necessary for this routine to be compatable with the    */
  165.     /*        Polygon shader.                                                    */
  166.     if (xmajor) {
  167.         alpha = (p1->x & 0xffff0000) | 0x00008000L;
  168.         alpha -= p1->x;
  169.         if (dx.x > 0) {                                /*    force |dx.x| = 1    */
  170.             dx.x = 0x10000;
  171.         } else {
  172.             dx.x = 0xffff0000;
  173.             alpha = -alpha;
  174.         }
  175.     } else {
  176.         alpha = (p1->y & 0xffff0000) | 0x00008000L;
  177.         alpha -= p1->y;
  178.         if (dx.y > 0) {                                /*    force |dx.y| = 1    */
  179.             dx.y = 0x10000;
  180.         } else {
  181.             dx.y = 0xffff0000;
  182.             alpha = -alpha;
  183.         }
  184.         dx.y = (dx.y > 0) ? 0x10000 : 0xffff0000;
  185.     }
  186.     fvscale(alpha, &dx, &fv);
  187.     fvadd(&fv, p1, &x);        /*    x.x or x.y should end up xxx.5    */
  188.     fvscale(alpha, &dc, &fv);
  189.     fvadd(&fv, c1, &c);
  190.     
  191.     /*    If necessary, draw the first point.    */
  192.     if ( (HiWord(p1->x) != HiWord(x.x)) || (HiWord(p1->y) != HiWord(x.y)) )
  193.         PlotC3dPoint(p1, c1);
  194.         
  195.     /*    Draw the line    */
  196.     for (i = 0; i < n; i++) {
  197.  
  198.         PlotC3dPoint(&x, &c);
  199.  
  200.         fvadd(&c, &dc, &c);
  201.         fvadd(&x, &dx, &x);
  202.     }
  203.     if ( (HiWord(x.y) != HiWord(p2->y)) && !xmajor)
  204.         DebugStr("\pC3dline didn't end on correct point!");
  205.     if ( xmajor && (HiWord(x.x) != HiWord(p2->x)) )
  206.         DebugStr("\pC3dline didn't end on correct point!");
  207. #if 0
  208.     if ( (HiWord(x.y) != HiWord(p2->y)) || (HiWord(x.x) != HiWord(p2->x)) )
  209.         DebugStr("\pC3dline cum roundoff error? didn't end on correct point!");
  210. #endif
  211. }
  212.  
  213. /*    ------------------------------------------------------------    */
  214. /*    Routines for the polygon shader.                                */
  215.  
  216. void
  217. ScanC3dLine(FixedVector *l, FixedVector *r, FixedVector *cl, FixedVector *cr)
  218. /*    
  219.     Draw a color blended scan line from the left l to the right r.  L has a
  220.     color of cl and r has a color cr.
  221.     
  222.     Note:    l and r must have the same y value.
  223.     
  224.     Warning:    This is a private function to the qd3d library and is
  225.                 highly subject to change or removal.
  226. */
  227. {
  228.     FixedVector    c, dc;
  229.     FixedVector    x, dx;
  230.     
  231.     int            n = HiWord(r->x) - HiWord(l->x);
  232.     Fixed        rw = Long2Fix((long)n);
  233.     int            i;
  234.     static Boolean        Debug = false;
  235.     
  236.     if (n <= 0)
  237.         return;
  238.         
  239.     if (Debug) {    /*    Speeds up overlap debugging    */
  240.         ForeColor(blackColor);
  241.         PenMode(patXor);
  242.         MoveTo(HiWord(l->x), HiWord(l->y));
  243.         LineTo(HiWord(r->x), HiWord(r->y));
  244.         LineTo(HiWord(r->x), HiWord(r->y));
  245.         return;
  246.     }
  247.  
  248.     fvcopy(cl, &c);
  249.     fvcopy(l, &x);
  250.     
  251.     fvsub(r, l, &dx);
  252.     rw = FixDiv(0x10000L, rw);
  253.     fvscale(rw, &dx, &dx);
  254. dx.x = 0x10000;    /*    This isn't exactly correct but it prevents cumulative
  255.                     roundoff error.     Ie. holes in the picture!  */
  256. dx.y = 0x00000000;
  257.  
  258.     fvsub(cr, cl, &dc);
  259.     fvscale(rw, &dc, &dc);
  260.  
  261.     for (i = 0; i < n; i++) {
  262.         fvadd(&x, &dx, &x);
  263.         if (i != n -1)
  264.             fvadd(&c, &dc, &c);
  265.         PlotC3dPoint(&x, &c);
  266.     }
  267.     if ( (HiWord(x.y) != HiWord(r->y)) || (HiWord(x.x) != HiWord(r->x)) )
  268.         DebugStr("\pScan line didn't end on correct point!");
  269. }
  270.  
  271. #define    succ(a)    ((a + 1) % n)
  272. #define    pred(a) ( (a == 0) ? n - 1 : (a-1) ) 
  273.  
  274. int
  275. next (int n, FixedVector v[], int s)
  276. /*
  277.     Returns the index into v of the next vertice in the polygon given
  278.     that the present vertice is s.  N is the number of vertices.
  279.     
  280.     If the value returned is < 0, the vertice tranversal has finished.
  281.     
  282.     Note:    N must be greater than 1.
  283.     
  284.     Warning:    This is a private function to the qd3d library and is
  285.                 highly subject to change or removal.
  286. */
  287. {
  288.     int        i = succ(s);
  289.     
  290.     while ((v[i].y == v[s].y) && (v[i].x == v[s].x) && (v[i].z == v[s].z)) {
  291.         if (i == s)
  292.             return (-1);
  293.         i = succ(i);
  294.     }
  295.     
  296.     if (v[i].y < v[s].y)
  297.         return (-1);
  298.     
  299.     return(i);
  300. }
  301.  
  302. int
  303. prev (int n, FixedVector v[], int s)
  304. /*
  305.     Returns the index into v of the previous vertice in the polygon given
  306.     that the present vertice is s.  N is the number of vertices.
  307.     
  308.     If the value returned is < 0, the vertice tranversal has finished.
  309.     
  310.     Note:    N must be greater than 1.
  311.     
  312.     Warning:    This is a private function to the qd3d library and is
  313.                 highly subject to change or removal.
  314. */
  315. {
  316.     int        i = pred(s);
  317.     
  318.     while ((v[i].y == v[s].y) && (v[i].x == v[s].x) && (v[i].z == v[s].z)) {
  319.         if (i == s)
  320.             /*    Must have been a single horz line. it won't be plotted.    */
  321.             return (-1);
  322.         i = pred(i);
  323.     }
  324.     
  325.     if (v[i].y < v[s].y)    /*    if headed up, the polygon is finished.    */
  326.         return (-1);
  327.     
  328.     return(i);
  329. }
  330.  
  331. void
  332. GouraudShade(int n, FixedVector v[], FixedVector c[])
  333. /*
  334.     Draws a Gouraud shaded (bi-linear color blend) polygon given the n
  335.     vertices v and the associated vertex colors c.
  336.     
  337.     Note:    This will only work on convex polygons.
  338.  
  339.     Warning:    This is a private function to the qd3d library and is
  340.                 highly subject to change or removal.
  341. */
  342. {
  343. /*
  344.     Note:    Whether the left side is really the left side is ambiguous.  The
  345.             only effect this ambiguity has is the parameter order of calling
  346.             the line fill function.  Leaving it ambiguous makes the code
  347.             simpler.
  348. */
  349.  
  350.                                 /*    Right side values.                        */
  351.     int        ri;                 /*    Current side target vertice index.        */
  352.     int        rCt;                /*    lines in the dda for this segment.        */
  353.     FixedVector
  354.             rx, rdx,            /*    Position and differential.                */
  355.             rc, rdc,            /*    Color and differential.                    */
  356.             rp, rpc;            /*    Plot position and color.                */
  357.             
  358.                                 /*    Left side values.                        */
  359.     int        li;                 /*    Current side target vertice index.        */
  360.     int        lCt;                /*    lines in the dda for this segment.        */
  361.     FixedVector
  362.             lx, ldx,            /*    Position and differential.                */
  363.             lc, ldc,            /*    Color and differential.                    */
  364.             lp, lpc;            /*    Plot position and color.                */
  365.     
  366.     FixedVector
  367.             fv;
  368.     int        ti;                    /*    Tempory vertice index.                    */
  369.     Fixed    tf;
  370.     Fixed    alpha;                /*    Amount of extrapolation necessary to 
  371.                                       get the dda's started off in the
  372.                                       correct place.                        */
  373.     int        agt0;                /*    Alpha is > 0.                            */
  374.     
  375.     int        i;
  376.     
  377.     if (n <= 2) return;
  378.     
  379.     /*    Find a top vertice    */
  380.     ti = 0;
  381.     for (i = 0+1; i < n; i++)
  382.         if (v[i].y < v[ti].y)
  383.             ti = i;
  384.  
  385.     /*    Start initial ri & li    */
  386.     ri = li = ti;
  387.     do {
  388.         ti = prev(n, v, ri);
  389.         if (ti < 0)
  390.             return;
  391.         if (v[ti].y == v[li].y)
  392.             ri = ti;
  393.         else
  394.             break;
  395.     } while (1);
  396.         
  397.     /*    Tell the dda's to start.    */
  398.     rCt = lCt = 0;
  399.  
  400.     /*    Line by line scan conversion    */
  401.     do {
  402.         if (lCt == 0) {
  403.             ti = next(n, v, li);
  404.             if (ti < 0)
  405.                 break;                                        /*    It's done!    */
  406.             fvsub(&v[ti], &v[li], &ldx);
  407.             fvsub(&(c[ti]), &(c[li]), &ldc);
  408.             lCt = HiWord(v[ti].y) - HiWord(v[li].y);
  409.             tf = FixDiv(Long2Fix(1L), ldx.y);
  410.             fvscale(tf, &ldc, &ldc);
  411.             fvscale(tf, &ldx, &ldx);                /*    ldx.y should = 1    */
  412. ldx.y = 0x10000;
  413.             alpha = (v[li].y & 0xffff0000) | 0x00008000L;                                    /*    .5    */
  414.             alpha -= v[li].y;
  415.             agt0 = alpha > 0 ? true : false;
  416.             fvscale(alpha, &ldx, &fv);
  417.             fvadd(&fv, &v[li], &lx);        /*    lx.y should end up xxx.5    */
  418.             fvscale(alpha, &ldc, &fv);
  419.             fvadd(&fv, &(c[li]), &lc);
  420.  
  421.             if ( !agt0 ) {
  422.                 /*    Use start point    */
  423.                 fvcopy(&(v[li]), &lp);
  424.                 fvcopy(&(c[li]), &lpc);
  425.             } else {
  426.                 /*    Use projected point */
  427.                 fvcopy(&lx, &lp);
  428. /*                fvcopy(&lc, &lpc);            /*    Projection may have overflowed/
  429.                                                 underflowed color so use...    */
  430.                 fvcopy(&(c[li]), &lpc);
  431.             }
  432.             li = ti;
  433.         }
  434.         if (rCt == 0) {
  435.             ti = prev(n, v, ri);
  436.             if (ti < 0)
  437.                 break;                                        /*    It's done!    */
  438.             fvsub(&v[ti], &v[ri], &rdx);
  439.             fvsub(&(c[ti]), &(c[ri]), &rdc);
  440.             rCt = HiWord(v[ti].y) - HiWord(v[ri].y);
  441.             tf = FixDiv(Long2Fix(1L), rdx.y);
  442.             fvscale(tf, &rdc, &rdc);
  443.             fvscale(tf, &rdx, &rdx);            /*    rdx.y should = 1.        */
  444. rdx.y = 0x10000;
  445.             alpha = (v[ri].y &0xffff0000) | 0x00008000L;     /*    .5    */
  446.             alpha -= v[ri].y;
  447.             agt0 = alpha > 0 ? true : false;
  448.             fvscale(alpha, &rdx, &fv);
  449.             fvadd(&fv, &v[ri], &rx);        /*    rx.y should end up xxx.5    */
  450.             fvscale(alpha, &rdc, &fv);
  451.             fvadd(&fv, &(c[ri]), &rc);
  452.  
  453.             if (!agt0) {
  454.                 /*    Use start point    */
  455.                 fvcopy(&(v[ri]), &rp);
  456.                 fvcopy(&(c[ri]), &rpc);
  457.             } else {
  458.                 /*    Use projected point */
  459.                 fvcopy(&rx, &rp);
  460. /*                fvcopy(&rc, &rpc);            /*    Projection may have overflowed/
  461.                                                 underflowed color so use...    */
  462.                 fvcopy(&(c[ri]), &rpc);
  463.             }
  464.             ri = ti;
  465.         }
  466.         
  467.         if ((lCt == 0) || (rCt == 0))
  468.             continue;                /*    This seems like a good idea.  ie.
  469.                                         don't do edges.                        */
  470.                                         
  471.         if (lp.x < rp.x)
  472.             ScanC3dLine(&lp, &rp, &lpc, &rpc);
  473.         else
  474.             ScanC3dLine(&rp, &lp, &rpc, &lpc);
  475.  
  476.         /*    Update the dda's    */
  477.         if ((--lCt) > 0) {
  478.             fvadd(&ldx, &lx, &lx);
  479.             fvadd(&lc, &ldc, &lc);
  480.             fvcopy(&lx, &lp);
  481.             fvcopy(&lc, &lpc);
  482.         }
  483.         if ((--rCt) > 0) {
  484.             fvadd(&rdx, &rx, &rx);
  485.             fvadd(&rc, &rdc, &rc);
  486.             fvcopy(&rx, &rp);
  487.             fvcopy(&rc, &rpc);
  488.         }
  489.     } while (1);
  490.     return;
  491.     
  492.     /*    The following notice may not be removed under any
  493.         circumstance.  See your licensing agreement.        */
  494.     asm {
  495.         dc.b    "gouraud Copyright 1991 Vividus Consulting"
  496.     }
  497. }